/*************************************************************************
	> File Name: stable_sort.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 日  9/26 17:18:05 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define COLOR(msg, code) "\033[0;" #code "m" msg "\033[0m"
#define YELLOW(msg)  COLOR(msg, 33)

#define swap(a, b) {\
    __typeof(a) _temp = a;\
    a = b;\
    b = _temp;\
}

void output(int *arr, int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        printf(" %d", arr[i]);
    }
    printf("]");
    return ;
}

#define TEST(arr, n, func, args...) {\
    int *nums = (int *)malloc(sizeof(int) * n);\
    memcpy(nums, arr, sizeof(int) * n);\
    output(nums, n);\
    printf("\n%s = ", #func);\
    long long begin = clock();\
    func(args);\
    long long end = clock();\
    output(nums, n);\
    printf(YELLOW("(%lld ms)") "\n", (end - begin) * 1000 / CLOCKS_PER_SEC);\
    free(nums);\
}

/*
 * 插入排序
 */
void insert_sort(int *arr, int n) {
    for (int i = 1; i < n; i++) {
        int tmp = arr[i];
        int j;
        for (j = i; j > 0 && arr[j - 1] > tmp; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = tmp;
    }
    return ;
}

/*
 * 冒泡排序
 */
void bubble_sort(int *arr, int n) {
    int times = 1; //标记是否发生了交换，如果出现某趟排序没有发生交换，则该数组已经有序
    for (int i = 1; i <= n && times; i++) { //排序的趟数
        times = 0;
        for (int j = 0; j < n - i; j++) {
            if (arr[j] < arr[j + 1]) continue;
            swap(arr[j], arr[j + 1]);
            times++;
        }
    }
    return ;
}

/*
 * 归并排序
 * 归并排序采用的是分治思想，所以使用递归的编程思想
 */
void merge_sort(int *arr, int left, int right) { 
    if (right - left <= 1) { //终止条件: 分到每组只有2个元素
        if (right - left == 1 && arr[right] < arr[left]) {
            swap(arr[left], arr[right]);
        }
        return ;
    }

    int mid = (left + right) >> 1;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);
    
    //对已经排好序的两个部分进行合并，即合并两个有序数组
    int *temp = (int *)malloc(sizeof(int) * (right - left + 1));
    int p1 = left;
    int p2 = mid + 1;
    int k = 0;//temp数组的增长下标
    while (p1 <= mid || p2 <= right) {
        if (p2 > right || (p1 <= mid && arr[p1] <= arr[p2])) {
            temp[k++] = arr[p1];
            p1++;
        } else {
            temp[k++] = arr[p2];
            p2++;
        }
    }
    
    //将临时数据的内容拷贝回上一层数组中
    memcpy(arr + left, temp, sizeof(int) * (right - left + 1));
    free(temp);
    return ;
}


void rand_int(int *arr, int n) {
    while (n--) arr[n] = rand() % 100;
    return ;
}

int main() {
    srand(time(0));
    #define max_op 20 
    int arr[max_op];
    rand_int(arr, max_op); //给数组随机生成值
    TEST(arr, max_op, insert_sort, nums, max_op);
    TEST(arr, max_op, bubble_sort, nums, max_op);
    TEST(arr, max_op, merge_sort, nums, 0, max_op - 1);
    #undef max_op 
    return 0;
}
